package arithmetic.LeetCode;

/**
 * 1143. 最长公共子序列
 * https://leetcode.cn/problems/longest-common-subsequence/description/?envType=study-plan-v2&envId=top-100-liked
 *
 * 给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
 *
 * 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
 *
 * 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
 * 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
 *
 *
 *
 * 示例 1：
 *
 * 输入：text1 = "abcde", text2 = "ace"
 * 输出：3
 * 解释：最长公共子序列是 "ace" ，它的长度为 3 。
 * 示例 2：
 *
 * 输入：text1 = "abc", text2 = "abc"
 * 输出：3
 * 解释：最长公共子序列是 "abc" ，它的长度为 3 。
 * 示例 3：
 *
 * 输入：text1 = "abc", text2 = "def"
 * 输出：0
 * 解释：两个字符串没有公共子序列，返回 0 。
 *
 *
 * @author jiangfeng on 2023/12/29
 */
public class longestCommonSubsequence {
    public static void main(String[] args) {
        System.out.println(new Solution().longestCommonSubsequence("ezupkr","ubmrapg"));
    }

    static class Solution {
        public int longestCommonSubsequence(String text1, String text2) {
            //先看哪个字符串短
            int len1 = text1.length();
            int len2 = text2.length();
            if(len2==1){
                return text1.contains(text2)?1:0;
            }
            if(len1==1){
                return text2.contains(text1)?1:0;
            }

            // i，j 表示 下标到s[i] t[j]时两个字符串公共最长长度。
            // s[i]!=t[j], dp[i][j] = Max(dp[i-1][j],dp[i][j-1])
            // s[i]==t[j]时, dp[i][j] = dp[i-1][j-1] + 1
            int[][] dp  = new int[len1+1][len2+1];
            // 初始值 // 初始值 这样时错的，因为 如果是从i=1，j=1 开始时，i=1 和j=1的所有边都得初始化
            // dp[0][0] = (text1.charAt(0)==text2.charAt(0))?1:0;
            // dp[0][1] = (text1.charAt(0)==text2.charAt(1)||dp[0][0]==1)?1:0;
            // dp[1][0] = (text1.charAt(1)==text2.charAt(0)||dp[0][0]==1)?1:0;

            for(int i = 1;i<=len1;i++){
                for(int j =1;j<=len2;j++){
                    if(text1.charAt(i-1)==text2.charAt(j-1)){
                        System.out.println(String.format("%s,%s ,%s",i,j,text1.charAt(i-1)));
                        dp[i][j] = dp[i-1][j-1]+1;
                    }else{
                        dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]);
                    }
                }
            }
            printDArray(dp);
            return dp[len1][len2];
        }

        public void printDArray(int[][] arr){
            for(int[] b:arr){
                for(int a:b){
                    System.out.print(a);
                    System.out.print(" ");
                }
                System.out.println();
            }
        }
    }
}
